Codes are known for converting information between different formats for different purposes. There are four generally recognized, broad purposes for coding: secrecy (“cryptography”), compression to reduce the space required to represent given data (“source coding”), formatting data for transmission over a physical medium (“line coding”), and formatting data to enable detection and correction of errors caused by unreliable storage or transmission mechanisms (“channel coding”).
A channel may be a single physical medium (“link”), or a concatenation of multiple links. Each such link may introduce noise into data by operating upon it in a different manner or in the same manner; regardless, the effects of such noise may be mathematically modeled, and detected or corrected using channel codes. In channel coding, error detection schemes generally operate by adding data to be stored or transmitted, such as a parity bit, checksum, or result of applying a hash (bit-mixing) function. Error correction typically operates using either an error-correction code (“ECC”), error detection in combination with an automatic repeat request (“ARQ”) requesting retransmission of additional data, or both. An ECC is usually either a block code that operates on independent, fixed-size data blocks (sometimes called “packets”) or a convolutional code that corrects streams of data via a sliding window.
Decoding a block code as known in the art requires ‘guessing’ a codeword by determining the codeword in a code book having the smallest Hamming distance (i.e. number of changed bits) to the received data block. Decoding a convolutional code, by contrast, requires applying to the received stream of data more sophisticated data models (such as a Markov model) and algorithms (such as the Viterbi algorithm) that operate on a probabilistic basis rather than a deterministic one. Thus, decoding block codes is generally faster than decoding convolutional codes.
The Shannon-Hartley theorem states that the capacity C of a data channel (in bits per second) equals the bandwidth of the channel (in Hz) multiplied by the base 2 logarithm of (1 plus the signal-to-noise power ratio of the channel). The noisy-channel coding theorem states that, for a noisy data channel having channel capacity C, the maximum rate R at which data may be transmitted over that channel is the ratio of C to (1 minus the binary entropy function for an acceptable probability of bit error). Because of this latter theorem, codes exist that allow the probability of error at the receiver to be made arbitrarily small precisely when R<C; that is, when the ratio R/C (sometimes called the “code rate”) is less than 1. Conversely, when the code rate is greater than 1, it is generally not possible to provide a code for which the probability of error at the receiver is arbitrarily small—decoding can still occur, albeit without sufficient data to prove that the decoded information is correct.
To achieve near-theoretical performance operate by a block code requires minimizing the binary entropy function, which in turn may require the block size to be arbitrarily large and thus computationally impractical. Thus, known systems using block codes do not approach channel capacity as closely as convolutional codes. Conversely, as noted above, known systems using convolutional codes do not decode as quickly as those using block codes.